#include"BiTree.h"

/*
insertNode:往一棵平衡二叉排序树中加入一个元素,使得二叉树任然具有平衡性
@root:指针,你要把元素加入到哪一棵树
@x:你要加入的元素的值
返回值:
返回加入元素后的二叉树的根节点的地址
*/

//递归插入代码
BiTNode *insertNode2(BiTNode *root,Datatype x)
{
    if(root == NULL)
    {
        //创建节点,保存x的值
        BiTNode *pt = (BiTNode *)malloc(sizeof(*pt));
        pt->data = x;
        pt->lchild = pt->rchild = NULL;
        pt->h = 1;
        return pt;
    }
    if(root->data > x)
    {
        //新增的元素的值比根节点小,应该放到根节点的左子树中去
        root->lchild = insertNode2(root->lchild,x);
        //往左子树上面新增加节点,可能会增加根节点的高度
        root->h = MAX( H(root->rchild),H(root->lchild) ) + 1;
        //往左子树上面新增加节点,有可能会导致root不平衡
        if(H(root->lchild) - H(root->rchild) > 1)
        {
            //导致了不平衡,需要进行平衡处理
            if(x > root->lchild->data)
            {
                //x是加入到左子节点的右边,需要对root进行先左后右的双向旋转
                return DoubleRotateLeftRight(root);
            }else if(x < root->lchild->data)
            {
                //x是加入到左子节点的左边,需要对root进行单向右旋
                return SingleRotateWithRight(root);
            }
        }
    }else 
    {
        //新增的元素的值比根节点大,应该放到根节点的右子树中去
        root->rchild = insertNode2(root->rchild,x);
        //往右子树上面新增加节点,可能会增加根节点的高度
        root->h = MAX( H(root->rchild),H(root->lchild) ) + 1;

        //往右子树上面新增加节点,有可能会导致root不平衡
        if(H(root->rchild) - H(root->lchild) > 1)
        {
            //导致了不平衡,需要进行平衡处理
            if(x > root->rchild->data)
            {
                //x是加入到右子节点的右边,需要对root进行单向左旋
                return SingleRotateWithLeft(root);    
            }else if(x < root->rchild->data)
            {
                //x是加入到右子节点的左边,需要对root进行先右后左的双向旋转
                return  DoubleRotateRightLeft(root);
            }
        }
    }
    return root;
}


/*
SingleRotateWithRight:对以k为根节点的二叉树进行单向右旋平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * SingleRotateWithRight(BiTNode *k)
{
    BiTNode* k1 = k->lchild;
    k->lchild = k1->rchild;
    k1->rchild = k;
    //重新计算k和k1的高度
    k->h = MAX(H(k->rchild),H(k->lchild)) +1;
    k1->h = MAX(H(k1->rchild),H(k1->lchild)) +1;
    return k1;   //k1作为旋转之后的新的根节点
}


/*
SingleRotateWithLeft:对以k为根节点的二叉树进行单向左旋平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * SingleRotateWithLeft(BiTNode *k)
{
    BiTNode* k1 = k->rchild;
    k->rchild = k1->lchild;
    k1->lchild = k;
    //重新计算k和k1的高度
    k->h = MAX(H(k->rchild),H(k->lchild)) +1;
    k1->h = MAX(H(k1->rchild),H(k1->lchild)) +1;
    return k1;   //k1作为旋转之后的新的根节点
}

/*
DoubleRotateLeftRight:对以k为根节点的二叉树进行双向旋转(先左后右)平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * DoubleRotateLeftRight(BiTNode *k)
{
    //先对不平衡节点的左子节点(k1)进行一个"单向左旋平衡处理"
    //对k1进行单向左旋的时候,会返回k1表示的那一棵子树的根节点
    k->lchild = SingleRotateWithLeft(k->lchild);   //返回子树的根节点成为了k在左子树

    //对不平衡节点k进行一个"单向右旋平衡处理"
    return SingleRotateWithRight(k);        //返回新的根节点
}

/*
DoubleRotateRightLeft:对以k为根节点的二叉树进行双向旋转(先右后左)平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * DoubleRotateRightLeft(BiTNode *k)
{
    //对不平衡节点的右子节点(k1)进行一个"单向右旋平衡处理"
    //对k1进行单向右旋的时候,会返回k1表示的那一棵子树的根节点
    k->rchild = SingleRotateWithRight(k->rchild);   //返回子树的根节点成为了k的右子树

    //对不平衡节点进行一个"单向左旋平衡处理"
    return SingleRotateWithLeft(k);          //返回新的根节点
}







/*
pre_order:以先序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void pre_order(BiTNode *t)
{
    if(t == NULL)
    {
        return;
    }
    //1.先访问根节点
    printf("%c(%d)  ",t->data,t->h);
    //2.再按照同用的方法(先根遍历)去访问根节点的左子树
    pre_order(t->lchild);
    //3.再按照同用的方法(先根遍历)去访问根节点的右子树
    pre_order(t->rchild);  
}

/*
mid_order:以中序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void mid_order(BiTNode *t)
{
    if(t == NULL)
    {
        return;
    }
    //1.先按照中序遍历的方法去访问根节点的左子树
    mid_order(t->lchild);
    //2.再访问根节点
    printf("%c  ",t->data);
    //3.再按照中序遍历的方法去访问根节点的右子树 
    mid_order(t->rchild); 
}

/*
last_order:以后序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void last_order(BiTNode *t)
{
    if(t == NULL)
    {
        return;
    }
    //1.先按照后序遍历的方法去访问根节点的左子树
    last_order(t->lchild);
    //3.再按照后序遍历的方法去访问根节点的右子树
    last_order(t->rchild);
    //2.再访问根节点
    printf("%c  ",t->data);
}

//返回以t为根节点的二叉树的高度、
int H(BiTNode *t)
{
    if(t == NULL)
    {
        return 0;
    }else 
    {
        return t->h;  //直接返回节点的高度
    }
}

/*
level_order:以层次遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void level_order2(BiTNode *t)
{
    if(t == NULL)
    {
        return;
    }
    //开辟一段连续的数组空间,用来模拟队列
    BiTNode *nodes[4096] = {0};  
    int rear = 0;   //下一个入队元素的下标
    int front = 0;  //下一个出队元素的下标

    //用来保存每一个节点所在的层次
    int h[4096] = {0};

    //把根节点入队列
    nodes[rear] = t;
    //入队元素的时候,需要需要记录当前元素的层次
    h[rear] = 1;  
    rear++;

    //用来保存将要出队的元素
    BiTNode *p = NULL; 

    while( front < rear)
    {
        //出队列一个元素
        p = nodes[front];
        
        //访问出队元素的数据
        printf("%c  ",p->data);

        //依次把出队元素的左子节点和右子节点依次入队列
        if(p->lchild != NULL)
        {
            nodes[rear] = p->lchild;
            h[rear] = h[front] + 1;     //子节点的高度是当前节点的高度+1
            rear++;
        }

        if(p->rchild != NULL)
        {
            nodes[rear] = p->rchild;
            h[rear] = h[front] + 1;     //子节点的高度是当前节点的高度+1
            rear++;
        }
        front++;
    }
    printf("\n");

    for(int i=0;i<rear;i++)
    {
        printf("%d  ",h[i]);
    }
    printf("\n");

}

//打印二叉树的4种遍历方式
void orderTree(BiTNode *tree)
{
    printf("先序遍历:");
    pre_order(tree);   
    printf("\n");

    printf("中序遍历:");
    mid_order(tree);   
    printf("\n");

    printf("后序遍历:");
    last_order(tree);   
    printf("\n");

    printf("层次遍历:");
    level_order2(tree);
}

